package 算法.LeetCode91.基础篇01;

/**
 * @author: 谢君臣
 * @create: 2021-02-01 11:28
 * @founction: XXXX
 */
public class Kmp {
    public static void main(String[] args) {
        char[] txt = "fgsdafasdf".toCharArray();
        char[] pat = "afasd".toCharArray();
        int i = KMP(txt, pat);
        System.out.println(i);
    }

    private static int KMP(char[] txt, char[] pat) {
        int[] next = getNext(pat);
        int i = 0;
        int j = 0;
        while (i < txt.length&&j<pat.length) {
            if (j==-1||txt[i] == pat[j]) {
                i++;
                j++;
            }else {
                j = next[j];
            }
        }
        if (j==pat.length)
            return i-j;
        else
            return -1;
    }

    //
    private static int[] getNext(char[] pat) {
        int[] next = new int[pat.length];
        int j = 0;
        int k = -1;
        next[0] = -1;
        while (j < pat.length - 1) {
            if (k == -1 || pat[j] == pat[k])
                next[++j] = ++k;
            else
                k = next[k];
        }
        return next;
    }

}

